package problem22;

import java.util.ArrayList;
import java.util.List;

//22.括号生成
//https://leetcode.cn/problems/generate-parentheses/

class Solution {
    List<String> ret = new ArrayList<>();
    StringBuffer str = new StringBuffer();
    int left = 0, right = 0;
    public List<String> generateParenthesis(int n) {
        dfs(n);
        return ret;
    }
    public void dfs(int n) {
        if(left > n || right > left) {
            return;
        }
        if(left == n && right == n) {
            ret.add(new String(str));
            return;
        }
        //添加左括号
        left++;
        str.append("(");
        dfs(n);
        left--;
        str.deleteCharAt(str.length()-1);

        //添加有括号
        str.append(")");
        right++;
        dfs(n);
        right--;
        str.deleteCharAt(str.length()-1);
    }
}